package fun.ticsmyc.question;

import org.junit.Test;

import java.util.HashMap;
import java.util.Map;
import java.util.Random;

/**
 * @author Ticsmyc
 * @package fun.ticsmyc.question
 * @date 2020-02-22 11:45
 *
 * 设计RandomPool结构
 * 【题目】 设计一种结构，在该结构中有如下三个功能：
 * insert(key)：将某个key加入到该结构，做到不重复加入。
 * delete(key)：将原本在结构中的某个key移除。 getRandom()：
 * 等概率随机返回结构中的任何一个key。
 * 【要求】 Insert、delete和getRandom方法的时间复杂度都是
 * O(1)
 *
 */
public class RandomPool {
    public static class Pool<K>{

        private Map<K,Integer> keyIndexMap;
        private Map<Integer,K> indexKeyMap;
        private int size;

        public Pool(){
            keyIndexMap = new HashMap<>();
            indexKeyMap = new HashMap<>();
            size=0;
        }

        public void insert(K key){
            if (!keyIndexMap.containsKey(key)) {
                keyIndexMap.put(key,size);
                indexKeyMap.put(size++,key);
            }
        }

        public void delete(K key){
            if(! keyIndexMap.containsKey(key)){
                return;
            }
            int index = keyIndexMap.get(key);
            //删
            keyIndexMap.remove(key);
            indexKeyMap.remove(index);
            size--;
            //填坑
            //获取最后一个元素的key  size--
            K lastOne = indexKeyMap.get(size);
            indexKeyMap.remove(size);
            keyIndexMap.put(lastOne,index);
            indexKeyMap.put(index,lastOne);
        }

        public K getRandom(){
            if(keyIndexMap.size()!=0){
                Random random = new Random();
                int index= random.nextInt(size);
                return indexKeyMap.get(index);
            }else{
                return null;
            }
        }

    }

    @Test
    public void test(){
        Pool<String> pool = new Pool<String>();
        pool.insert("zuo");
        pool.insert("cheng");
        pool.insert("yun");
        pool.delete("zuo");
        System.out.println(pool.getRandom());
        System.out.println(pool.getRandom());
        System.out.println(pool.getRandom());
        System.out.println(pool.getRandom());
        System.out.println(pool.getRandom());

    }
}
